﻿// 3505. 最长ZigZag子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/3508/

一个整数序列的子序列是指从给定序列中随意地（不一定连续）去掉若干个整数（可能一个也不去掉）后所形成的整数序列。

对于一个整数序列 x1,x2,…,xn，如果满足下列两个条件之一：

∀i∈[1,n−1]，当 i%2==1 时，xi−xi+1为正，当 i%2==0 时，xi−xi+1 为负。
∀i∈[1,n−1]，当 i%2==1 时，xi−xi+1为负，当 i%2==0时，xi−xi+1为正。
那么，我们就称这个整数序列为 ZigZag 序列。

换句话说，ZigZag 序列就是一个序列内元素在增大和减小之间不断切换的序列。

例如 1,7,4,9,2,5就是一个 ZigZag 序列。

现在，给定一个长度为 n 的整数序列，请你求出它的最长 ZigZag 子序列的长度。

输入格式
第一行包含整数 n。

第二行包含 n个整数。

输出格式
输出一个整数，表示最长 ZigZag 子序列的长度。

数据范围
1≤n≤50
,
序列内元素取值范围 [1,1000]
。

输入样例：
6
1 7 4 9 2 5
输出样例：
6
*/
int main()
{
    std::cout << "Hello World!\n";
}

 